package com.example.leetcode.StackSimple;

import org.junit.Test;

import java.util.Stack;

public class B_栈实现队列 {
    /**
     * Implement Queue using Stacks
     * 思路一： 
     * 将stack1作为存储空间，将stack2作为临时缓冲区 
     * 入队时：直接压入stack1 
     * 出队时：将stack1中的元素依次压入stack2中，再将stack2的栈顶元素弹出，最后将stack2中的元素再压回给stack1
     * 思路二： 
     * stack1专注push ,stack专注pop
     * 入队时：直接存入stack1 
     * 出队时：判断stack2是否为空，如果stack2是空，将stack1依次压入stack2，并弹出最上面的元素，如果stack2不为空，直接弹出最上面的元素
     * @param args
     */
    public static void main(String[] args) {

    }
}

class MyQueue {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        while (!stackIn.isEmpty()) {
            Integer pop = stackIn.pop();
            stackOut.push(pop);
        }
        Integer pop = stackOut.pop();
        backStack(stackOut, stackIn);
        return pop;
    }


    /**
     * Get the front element.
     */
    public int peek() {
        while (!stackIn.isEmpty()) {
            Integer pop = stackIn.pop();
            stackOut.push(pop);
        }
        Integer peek = stackOut.peek();
        backStack(stackOut, stackIn);
        return peek;
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        if (!stackIn.isEmpty() || !stackOut.isEmpty()) {
            return true;
        }
        return false;
    }

    /**
     * 恢复stackIn可以push的初始状态 ; StackOut -> Stackin
     */
    public void backStack(Stack out, Stack in) {
        while (!out.isEmpty()) {
            in.push(out.pop());
        }
    }
}

class MyQueue2 {
    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    /**
     * Initialize your data structure here.
     */
    public MyQueue2() {
        stackIn = new Stack<>();
        stackOut = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        stackIn.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (!stackOut.isEmpty()) {
            return stackOut.pop();
        }
        while (!stackIn.isEmpty()) {
            Integer pop = stackIn.pop();
            stackOut.push(pop);
        }
        Integer pop = stackOut.pop();
        return pop;
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (!stackOut.isEmpty()) {
            return stackOut.peek();
        }
        while (!stackIn.isEmpty()) {
            Integer pop = stackIn.pop();
            stackOut.push(pop);
        }
        Integer peek = stackOut.peek();
        return peek;
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return !(!stackIn.isEmpty() || !stackOut.isEmpty());
    }

    /**
     * 恢复stackIn可以push的初始状态 ; StackOut -> Stackin
     */
    public void backStack(Stack out, Stack in) {
        while (!out.isEmpty()) {
            in.push(out.pop());
        }
    }
}
